﻿#include <iostream>
#include <queue>
using namespace std;

//Definition for singly-linked list.
struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
 };
 
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
    {
        ListNode* newhead = new ListNode(0);
        ListNode* cur1 = l1;
        ListNode* cur2 = l2;
        ListNode* tail = newhead;
        int t = 0;
        while (cur1 || cur2 || t)
        {
            if (cur1)
            {
                t += cur1->val;
                cur1 = cur1->next;
            }
            if (cur2)
            {
                t += cur2->val;
                cur2 = cur2->next;
            }
            //ListNode* newnode = new ListNode(t % 10);//个位
            //tail->next = newnode;
            //tail = newnode;
            tail->next = new ListNode(t % 10);
            tail = tail->next;
            t /= 10;
        }

        tail = newhead->next;
        delete newhead;

        return tail;
    }
};

class Solution {
public:
    ListNode* swapPairs(ListNode* head)
    {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* newhead = new ListNode(0);
        newhead->next = head;

        ListNode* prev = newhead;
        ListNode* cur = prev->next;
        ListNode* next = cur->next;
        ListNode* nnext = next->next;
        while (cur && next)
        {
            //交换顺序
            prev->next = next;
            next->next = cur;
            cur->next = nnext;

            //重新赋值
            prev = cur;
            cur = nnext;
            if (cur) next = cur->next;
            if (next) nnext = next->next;

        }
        cur = newhead->next;
        delete newhead;
        return cur;
    }
};

//递归
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head)
    {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* next = head->next;
        ListNode* nnext = next->next;
        ListNode* tmp = swapPairs(head->next->next);
        next->next = head;
        head->next = tmp;
        return next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head)
    {
        // 处理边界情况
        if (head == nullptr || head->next == nullptr || head->next->next == nullptr) return;
        // 1.找到链表的中间节点
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 2.把后面的部分逆序 头插
        ListNode* head2 = new ListNode(0);
        ListNode* cur = slow->next;
        slow->next = nullptr;//断开
        while (cur)
        {
            ListNode* next = cur->next;
            cur->next = head2->next;
            head2->next = cur;
            cur = next;
        }
        // 3.合并两个链表
        ListNode* ret = new ListNode(0);
        ListNode* prev = ret;
        ListNode* cur1 = head, * cur2 = head2->next;
        while (cur1)
        {
            prev->next = cur1;
            cur1 = cur1->next;
            prev = prev->next;

            if (cur2)
            {
                prev->next = cur2;
                prev = prev->next;
                cur2 = cur2->next;
            }
        }

        delete head2;
        delete ret;

    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    struct cmpare
    {
        bool operator()(const ListNode* l1, const ListNode* l2)
        {
            //l1 > l2 向下调整
            return l1->val > l2->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        // 创建⼀个⼩根堆
        priority_queue<ListNode*, vector<ListNode*>, cmpare> heap;
        //让所有的头结点进入小根堆
        for (auto l : lists)
        {
            if (l) heap.push(l);
        }

        //合并
        ListNode* ret = new ListNode(0);
        ListNode* prev = ret;
        while (!heap.empty())
        {
            ListNode* top = heap.top();
            heap.pop();
            prev->next = top;
            prev = top;

            if (top->next) heap.push(top->next);
        }

        prev = ret->next;
        delete ret;
        return prev;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * ListNode *next;
 * ListNode() : val(0), next(nullptr) {}
 * ListNode(int x) : val(x), next(nullptr) {}
 * ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        return merge(lists, 0, lists.size() - 1);
    }
    ListNode* merge(vector<ListNode*>& lists, int left, int right)
    {
        if (left > right) return nullptr;
        if (left == right) return lists[left];
        // 1. 平分数组
        int mid = left + right >> 1;
        // [left, mid] [mid + 1, right]
        // 2. 递归处理左右区间
        ListNode* l1 = merge(lists, left, mid);
        ListNode* l2 = merge(lists, mid + 1, right);
        // 3. 合并两个有序链表
        return mergeTowList(l1, l2);
    }
    ListNode* mergeTowList(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;
        // 合并两个有序链表
        ListNode head;
        ListNode* cur1 = l1, * cur2 = l2, * prev = &head;
        head.next = nullptr;
        while (cur1 && cur2)
        {
            if (cur1->val <= cur2->val)
            {
                prev = prev->next = cur1;
                cur1 = cur1->next;
            }
            else
            {
                prev = prev->next = cur2;
                cur2 = cur2->next;
            }
        }
        if (cur1) prev->next = cur1;
        if (cur2) prev->next = cur2;
        return head.next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * ListNode *next;
 * ListNode() : val(0), next(nullptr) {}
 * ListNode(int x) : val(x), next(nullptr) {}
 * ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    ListNode* reverseKGroup(ListNode* head, int k)
    {
        // 1. 先求出需要逆序多少组
        int n = 0;
        ListNode* cur = head;
        while (cur)
        {
            cur = cur->next;
            n++;
        }
        n /= k;
        // 2. 重复 n 次：⻓度为 k 的链表的逆序即可
        ListNode* newHead = new ListNode(0);
        ListNode* prev = newHead;
        cur = head;
        for (int i = 0; i < n; i++)
        {
            ListNode* tmp = cur;
            for (int j = 0; j < k; j++)
            {
                ListNode* next = cur->next; cur->next = prev->next;
                prev->next = cur;
                cur = next;
            }
            prev = tmp;
        }
        // 把不需要翻转的接上
        prev->next = cur;
        cur = newHead->next;
        delete newHead;
        return cur;
    }
};